package com.cdream.basic.algorithm.leetcode.tree;

public class Question96 {
    // G(n) = 长度为n时，树的数量
    // F(i,n) = 以i为根节点时，树的数量
    // G(n) = sum(F(1,n)...F(n,n))
    // F(i,n) = G(i-1) * G(n-i)
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }

    public static void main(String[] args) {
        System.out.println(new Question96().numTrees(3));
    }

}


